package com.txy.sort;

public class QuickSort2 {
    public static void quickSort(int[] arr, int start, int end) {
        if(start>=end) return ;
        int pivot = pivot(arr, start, end);
        quickSort(arr, start ,pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    // 单边循环
    private static int pivot(int[] arr, int start, int end) {
        int pivot = arr[start];
        int mark = start;
        for(int i = start + 1; i<= end;i++) {
            if(arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[start] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
    public static void main(String[] args) {
        int[] arr = new int[] {4,7,3,5,6,2,8,1};
        quickSort(arr,0, arr.length-1);
        System.out.println(arr);
    }
}
